// 设计要点 / Invariants：
//  - 物理缓冲区 `_buf.length` 是“容量(capacity)”，不是“有效长度”；有效长度 = 内容长度 = `length`。
//  - 区间布局：
//      [0, _gapStart)           —— 左段内容（连续）
//      [_gapStart, _gapEnd)     —— gap（空洞区，不计入内容长度）
//      [_gapEnd, _buf.length)   —— 右段内容（连续）
//  - 所有对外位置（pos/start/end）均是“内容坐标系”，不计入 gap，等价于 Flutter `String.length` 的 UTF-16 码元语义。
//  - 移动 gap 时保持段内相对顺序，采用 `List.setRange` 做安全、有序的搬移。
//  - 扩容时维持上述不变量，并尽量成倍扩容以减少拷贝次数。
//  - 变更（插入/删除）后会递增 `version` 并失效缓存（整串与拆行）。
//
// 复杂度（摊还）：
//  - `insert` / `delete`：O(|移动段|) + 摊还 O(1) 扩容；通常接近 O(1)（当 gap 就位且足够大）。
//  - `getText`：O(n)（首次或版本变化后重建缓存）；缓存命中则 O(1)。
//  - `getLines`：基于 `getText()` 的 `split('\n')`，同上缓存策略。
//
// 注意事项：
//  - 本实现按 UTF-16 码元计数（即 Dart `String.length` 语义）。含表情/组合字符（grapheme cluster）情况下，
//    光标/选择应由上层按“字符簇”管理；本类仅保证码元级别的安全与一致性。
//  - 非线程安全。请在单线程/单任务上下文中使用或自行加锁。
//  - `setRange` 在同一列表上使用时能正确处理重叠区（Dart 标准库保证），因此移动段是安全的。
//  - 本文件仅暴露：`length`, `insert`, `delete`, `getText`, `getLines`, `version`。
//    你可按需扩展诸如 `clear` / `replaceRange` / `substring` 等便捷 API（未包含于本版本）。
//
// 使用示例：
//   final buf = TextBuffer('Hello');
//   buf.insert(5, ' World');  // "Hello World"
//   buf.delete(5, 6);         // 删除空格 -> "HelloWorld"
//   print(buf.getText());     // 缓存首建后再次调用 O(1)
//   print(buf.length);        // UTF-16 码元长度
//
// --- Implementation starts below ---

import 'dart:math' as math;

/// Gap Buffer 文本缓冲结构。
///
/// 内部以 `_buf` 存储 UTF-16 码元（`int`），并维护 gap 区间 `[_gapStart, _gapEnd)`。
/// 对外一切索引均为“内容坐标系”（不含 gap），与 Dart `String.length` 语义一致。
class TextBuffer {
  // =========================
  // 存储与 gap 指针
  // =========================

  /// 物理存储（UTF-16 码元）。容量 `_buf.length` ≥ 内容长度。
  List<int> _buf;

  /// gap 区间起止：[_gapStart, _gapEnd)
  int _gapStart;
  int _gapEnd;

  // =========================
  // 扩容策略参数（可按需调优）
  // =========================

  /// 初始预留的 gap 大小（避免小文本立即扩容）。
  static const int _kDefaultGap = 256;

  /// 每次至少增长的 gap 空间。
  static const int _kMinGrow = 256;

  /// 成倍扩容的阈值因子（减少扩容次数）。
  static const int _kGrowFactor = 2;

  // =========================
  // 版本与缓存
  // =========================

  /// 当文本发生任何变更时递增，用于判定缓存是否失效。
  int _version = 0;

  /// 当前版本号（只读）。
  int get version => _version;

  /// 整串文本缓存。
  String? _cachedText;
  int _cachedTextVersion = -1;

  /// 拆行缓存。
  List<String>? _cachedLines;
  int _cachedLinesVersion = -1;

  // =========================
  // 构造
  // =========================

  /// 以可选初始文本构造。
  ///
  /// 初始时将文本放入左段，右侧整体作为 gap，以便后续尾插高效。
  TextBuffer([String initialText = ''])
      : _gapStart = 0,
        _gapEnd = 0,
        _buf = List<int>.filled(
          initialText.codeUnits.length + _kDefaultGap,
          0,
          growable: false,
        ) {
    final units = initialText.codeUnits;
    // 初始文本放到左段 [0, units.length)
    _buf.setRange(0, units.length, units, 0);
    _gapStart = units.length;
    _gapEnd = _buf.length; // 剩余全部作为 gap
    _debugCheckInvariants();
  }

  // =========================
  // 公共 API
  // =========================

  /// 当前“有效文本长度”（UTF-16 码元个数，不包含 gap）。
  int get length => _gapStart + (_buf.length - _gapEnd);

  /// 返回整段文本（带版本缓存）。
  ///
  /// 首次或文本变更后会重建字符串；若版本未变则直接返回缓存（O(1)）。
  String getText() {
    if (_cachedText != null && _cachedTextVersion == _version) {
      return _cachedText!;
    }
    final left = String.fromCharCodes(_buf.getRange(0, _gapStart));
    final right = String.fromCharCodes(_buf.getRange(_gapEnd, _buf.length));
    final text = left + right;
    _cachedText = text;
    _cachedTextVersion = _version;
    return text;
  }

  /// 以 '\n' 拆分为多行并缓存结果。
  ///
  /// 说明：为了简单可靠，基于 `getText()` 后再 `split('\n')`，而非在缓冲层内做增量行索引。
  List<String> getLines() {
    if (_cachedLines != null && _cachedLinesVersion == _version) {
      return _cachedLines!;
    }
    final lines = getText().split('\n');
    _cachedLines = lines;
    _cachedLinesVersion = _version;
    return lines;
  }

  /// 在内容坐标 `pos` 处插入 `text`。
  ///
  /// - `pos` 范围：`0..length`（含端点）。
  /// - 若 `text.isEmpty` 则直接返回。
  ///
  /// 抛出：
  /// - `RangeError`：当 `pos` 越界。
  void insert(int pos, String text) {
    if (text.isEmpty) return;
    if (pos < 0 || pos > length) {
      throw RangeError('Invalid insert position: $pos (len=$length)');
    }
    final units = text.codeUnits;

    // 1) 将 gap 挪到目标位置（pos）
    _moveGapTo(pos);

    // 2) 确保 gap 足够容纳要写入的码元
    _ensureGap(units.length);

    // 3) 将文本写入 gap 左侧，并推进 gapStart
    _buf.setRange(_gapStart, _gapStart + units.length, units, 0);
    _gapStart += units.length;

    _bumpVersionAndInvalidate();
    _debugCheckInvariants();
  }

  /// 删除半开区间 `[start, end)`（内容坐标）。
  ///
  /// 允许 `start == end`（无操作），若 `start > end` 会自动交换两端。
  ///
  /// 抛出：
  /// - `RangeError`：当区间与内容长度不相容。
  void delete(int start, int end) {
    if (start == end) return;
    if (start > end) {
      final t = start;
      start = end;
      end = t;
    }
    if (start < 0 || end > length) {
      throw RangeError('Invalid delete range: [$start, $end) (len=$length)');
    }

    // 1) 将 gap 挪到删除起点 start
    _moveGapTo(start);

    // 2) “吞掉”右侧 [start, end) 内容：扩张 gap 到右边
    final count = end - start;
    _gapEnd += count;

    _bumpVersionAndInvalidate();
    _debugCheckInvariants();
  }

  // =========================
  // 内部工具：gap 维护与缓存管理
  // =========================

  /// 确保 gap 至少有 `need` 个码元的空间，不足则扩容。
  ///
  /// 扩容思路：
  /// - 新容量 `newCap` 至少为：当前内容长度 + max(need, `_kMinGrow`)。
  /// - 若低于 `_buf.length * _kGrowFactor`，则取倍增以减少未来扩容次数。
  /// - 新缓冲区保持 gap 仍从 `newGapStart = _gapStart` 开始（即 gap 的“位置”稳定）。
  void _ensureGap(int need) {
    final gapSize = _gapEnd - _gapStart;
    if (gapSize >= need) return;

    final contentLen = length;
    final minExtra = math.max(need, _kMinGrow);
    var newCap = contentLen + minExtra;

    // 倍增策略：尽量一次扩大到至少 2 倍容量，降低后续扩容频率
    if (newCap < _buf.length * _kGrowFactor) {
      newCap = _buf.length * _kGrowFactor;
    }

    final newBuf = List<int>.filled(newCap, 0, growable: false);

    // 计算新的 gap 区间：从原 _gapStart 开始，长度 = newCap - contentLen
    final newGapStart = _gapStart;
    final newGapEnd = newGapStart + (newCap - contentLen);

    // 拷贝左段 [0, _gapStart)
    newBuf.setRange(0, _gapStart, _buf, 0);

    // 拷贝右段到新 gap 之后
    final rightCount = _buf.length - _gapEnd; // 右段长度
    final newRightStart = newGapEnd;
    newBuf.setRange(newRightStart, newRightStart + rightCount, _buf, _gapEnd);

    // 切换到新缓冲区
    _buf = newBuf;
    _gapStart = newGapStart;
    _gapEnd = newGapEnd;
  }

  /// 将 gap 挪动到目标内容坐标 `targetPos`。
  ///
  /// 通过搬移两侧内容实现：
  /// - 若 `targetPos < _gapStart`：把左侧 `[targetPos, _gapStart)` 搬到 gap 右端之前；
  /// - 否则（右移）：把右侧 `[_gapEnd, _gapEnd + moveCount)` 搬到 gap 左端。
  void _moveGapTo(int targetPos) {
    // 规范化：钳制到 [0, length]
    if (targetPos < 0) targetPos = 0;
    if (targetPos > length) targetPos = length;

    final current = _gapStart;
    if (targetPos == current) return;

    if (targetPos < current) {
      // 左移 gap：把 [targetPos, current) 搬到 gap 右端的前面
      final moveCount = current - targetPos;
      final dstStart = _gapEnd - moveCount;
      _buf.setRange(dstStart, _gapEnd, _buf, targetPos);
      _gapStart = targetPos;
      _gapEnd = dstStart;
    } else {
      // 右移 gap：把右段的前 moveCount 个码元搬到 gap 左端
      final moveCount = targetPos - current;
      _buf.setRange(_gapStart, _gapStart + moveCount, _buf, _gapEnd);
      _gapStart += moveCount;
      _gapEnd += moveCount;
    }
  }

  /// 版本递增并失效所有缓存。
  void _bumpVersionAndInvalidate() {
    _version++;
    _cachedTextVersion = -1;
    _cachedLinesVersion = -1;
    _cachedText = null;
    _cachedLines = null;
  }

  /// 仅在调试/断言模式下检查不变量、边界与读段安全性。
  void _debugCheckInvariants() {
    assert(_gapStart >= 0 && _gapStart <= _gapEnd && _gapEnd <= _buf.length);

    final leftCount = _gapStart;
    final rightCount = _buf.length - _gapEnd;
    final contentLen = leftCount + rightCount;

    assert(contentLen == length);

    // 读出两段范围，不应越界（仅触发范围检查；避免实际分配）
    assert(() {
      // 访问迭代器本身即可触发范围验证，不需要接收变量
      _buf.getRange(0, _gapStart);
      _buf.getRange(_gapEnd, _buf.length);
      return true;
    }());
  }
}
